home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 6115 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.4 KB
  1. Path: po.CWRU.Edu!mab22
  2. From: mab22@po.CWRU.Edu (Michael A. Balfour)
  3. Newsgroups: comp.lang.c
  4. Subject: Re:  Perfect Hash Functions
  5. Date: 22 Feb 1996 19:57:55 GMT
  6. Organization: Case Western Reserve University, Cleveland, OH (USA)
  7. Message-ID: <4gihs3$bnl@madeline.INS.CWRU.Edu>
  8. Reply-To: mab22@po.CWRU.Edu (Michael A. Balfour)
  9. NNTP-Posting-Host: kanga.ins.cwru.edu
  10.  
  11.  
  12. Well,
  13.  
  14. it looks like I beat everybody else to answering my own question.
  15. However, if anybody else has needed to solve a similar problem, here's
  16. what I found:  there is a very good paper titled "An optimal algorithm
  17. for generating minimal perfect hash functions" which describes how to go
  18. about finding the perfect hash function for a set of strings.  The
  19. algorithm also allows you to keep the strings' hash values in the same
  20. order as the strings.  For example, you could map the strings
  21. ("JAN","FEB","MAR","APR","MAY","JUN") to the integers 0-5 respectively.
  22.  
  23. Pretty cool!
  24.  
  25. This paper can be found at ftp.cs.uq.oz.au, and it is written by
  26. Zbigniew Czech, George Havas, and Bohdan Majewski.  Unfortunately, it
  27. doesn't come with source code.  :(  Hope you remember your graph
  28. theory...
  29.  
  30. Mike Balfour
  31.  
  32. -- 
  33. ----------------------------------+--------------------------------
  34. Mike Balfour, Partner             | BS/MS Graduate - ECMP
  35. Overload Engineering              | Case Western Reserve University
  36. "New Ideas for a Brighter Future" | Cleveland, OH
  37.